Current approximate Coarse Correlated Equilibria (CCE) algorithms struggle with equilibrium approximation for games in large stochastic environments but are theoretically guaranteed to converge to a strong solution concept. In contrast, modern Reinforcement Learning (RL) algorithms provide faster training yet yield weaker solutions. We introduce Exp3-IXrl - a blend of RL and game-theoretic approach, separating the RL agent's action selection from the equilibrium computation while preserving the integrity of the learning process. We demonstrate that our algorithm expands the application of equilibrium approximation algorithms to new environments. Specifically, we show the improved performance in a complex and adversarial cybersecurity network environment - the Cyber Operations Research Gym - and in the classical multi-armed bandit settings.

This paper proposes a new notion of Markov α-potential games to study Markov games. Two important classes of practically significant Markov games, Markov congestion games and the perturbed Markov team games, are analyzed in this framework of Markov α-potential games, with explicit characterization of the upper bound for α and its relation to game parameters. Moreover, any maximizer of the α-potential function is shown to be an α-stationary Nash equilibrium of the game. Furthermore, two algorithms for the Nash regret analysis, namely the projected gradient-ascent algorithm and the sequential maximum improvement algorithm, are presented and corroborated by numerical experiments. Key words: Markov α-potential games; Markov potential games; Multi-agent reinforcement learning; Nash-regret; Markov congestion games; Perturbed Markov team games; Projected gradient-ascent algorithm; Sequential maximum improvement.